package com.lmz.project.redis.arithmetic.sort;

public class HeapSort {
    //i的父节点位置 parent = (i-1)/2
    //i的左节点位置 left = i*2 +1
    //i的右节点位置 right = i*2 +2
    public static int size = 5;

    // i位置的数，向上调整大根堆
    public static void heapInsert(int[] nums, int i) {
        while (nums[i] > nums[(i - 1) / 2]) {
            swap(nums, i, (i - 1) / 2);
            i = ((i - 1) / 2);
        }
    }


    // i位置的数，向下调整大根堆
    public static void heapify(int[] nums, int i,int size) {
        while (i * 2 + 1 < size) {
            int l = i * 2 + 1;
            int leftNum = l < size && nums[l] > nums[i] ? l : i;
            int rightNum = l + 1 < size && nums[l+1] > nums[i] ? l + 1 : i;
            //左右节点种的最大值
            int max = nums[leftNum] > nums[rightNum] ? leftNum : rightNum;
            //如果相等就不需要交换
            if (i == max) {
                break;
            } else {
                //将大节点交换到父节点位置
                swap(nums, i, max);
                i = max;
            }
        }
    }


//    public static void heapify(int[] arr, int i, int size) {
//        int l = i * 2 + 1;
//        while (l < size) {
//            int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
//            best = arr[best] > arr[i] ? best : i;
//            if (best == i) {
//                break;
//            }
//            swap(arr,best, i);
//            i = best;
//            l = i * 2 + 1;
//        }
//    }

    //构建大根堆 从顶到底
    public static void heapSort1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        int size = arr.length;
        //每次把顶部最大元素与最后的位置交换，然后向下调整，保证下一次的剩余数组仍然是大根堆
        while (size > 1) {
            swap(arr,0, --size);
            heapify(arr,0,size);
        }
    }


    //构建大根堆，从底到顶
    public static void heapSort2(int[] arr){
        for (int i = arr.length-1; i >=0 ; i--) {
            heapify(arr,i,arr.length);
        }
        int size = arr.length;
        while (size > 1) {
            swap(arr,0, --size);
            heapify(arr,0,size);
        }
    }


    public static void swap(int[] sums, int a, int b) {
        int temp = sums[a];
        sums[a] = sums[b];
        sums[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1, 5, 2, 4, 3};
//        heapSort1(arr);
        heapSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
